package main

import (
	"fmt"
)

//给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

/*示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n保证是有效的。
*/
// 思路实现方法
// 使用快慢指针法，遍历节点，将两次遍历和合并为一次，使用快指针和慢指针之间的关系来完成

type ListNode19 struct {
	Val int
	Next* ListNode19
}

func removeNthFromEnd(head *ListNode19, n int) *ListNode19 {
	first :=head
	second :=head
	var before *ListNode19
	for i:=0;i<n;i++{
		first=first.Next
	}
	// 找到倒数第二个位置
	for first!=nil{
		first=first.Next
		before=second
		second=second.Next
	}
	// 删除当前位置的节点
	fmt.Println(second.Val)
    if second == head {  // 如果删除头节点，需要特殊处理
        return second.Next
    }
	before.Next =before.Next.Next // 删除尾部节点不需要特殊处理
	return head
}
  func main(){
  	var l1 ListNode19
  	var l2 ListNode19
  	var l3 ListNode19
  	var l4 ListNode19
  	var l5 ListNode19
  	l1.Val=1
  	l2.Val=2
  	l3.Val=3
  	l4.Val=4
  	l5.Val=5
  	l1.Next=&l2
  	l2.Next=&l3
  	l3.Next=&l4
  	l4.Next=&l5
  	removeNthFromEnd(&l1,2)
  }


